1. Field of the Invention
This invention relates to improvements in memory systems, and more particularly, to improvements in methods for managing memory systems, and still more particularly to an improved method for segregating active and stable blocks for improved memory response time.
2. Background Information
The development of storage management systems has a long history with many related branches of research. Over the years, a great deal of attention has been given to the allocation and deallocation of memory structures. Many memory structures of interest are shown by Deitel, H. M., An Introduction to Operating Systems, Addison-Wesley, Massachusetts, Chapter 7, 1982. Other major issues are discussed by knuth, D., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968. The invention herein described is concerned primarily with computer systems having heap managed memories, and is used together with or independently from a garbage collection scheme. A "heap managed" memory is one in which the memory is allocated and freed (either explicitly or implicitly) without regard to the temporal order or the size of the memory unit under consideration. A garbage collected memory is one in which usable memory is automatically reclaimed, and the memory may be reorganized from time to time to efficiently utilize the space of the memory, as needed. A survey of garbage collection techniques and related background materials is presented by Cohen, J., "Garbage Collection of Linked Data Structures", Computing Surveys, Vol. 13, No. 3, September, 1981, pp. 341-367. P. Bishop discusses garbage collection in very large address spaces in "Garbage Collection in a Very Large Address Space", Massachusetts Institute of Technology, Working Paper 111, September 1975.
Additionally, the overall size of a virtual memory space is often of concern, since garbage collection costs increase with the size of the space being collected, not with the amount of garbage being reclaimed.
In the operation of a typical memory system and associated central processing unit (CPU), the CPU requests the allocation of memory space as needed. Often, the allocation of the memory is done in a virtual address space. As the virtual address space becomes fully allocated, eventually requests for additional space must be denied, until reusable space in the previously allocated virtual address space has been identified and reclaimed.
As used herein, the term "physical memory" means the actual physical memory, including the main memory, usually RAM semiconductor devices, and the backing store, usually a paging disk. The term "virtual address space" is used to mean a uniform linear, and homogenous apparent memory space.
Generally in memory systems of the type to which the invention pertains, portions of memory are allocated in "blocks" of size specified by the CPU. Each block has a header in which various pieces of information are contained pertaining to the block, including, for example, the identification of the block its size, and other things which may be of interest. Also contained in the block header is a field containing a reference count. The reference count of a block indicates the number of references to the block from any other block, or itself. One form of reference count is shown by Deutsch et al., "An Efficient, Incremental, Automatic Garbage Collector", CACM, Vol. 19, No. 9, September, 1976, pp. 522-526. In the type of memory to which the method of this invention pertains, when a block is initially allocated, it has a reference count of zero. Any time a new reference is established, the reference count is incremented. When a reference within a block is destroyed, the reference count of the target block is decremented. Except when a block is originally created, when the reference count of a block is decremented to zero, the block is considered to be garbage, and the space it occupies can be reclaimed.
In the memory management systems in the past, as blocks were allocated and deallocated, often pages containing very few blocks were paged out to disk to make room for further block allocation. As the need arose for access to the paged out blocks, usually, some additional page in the main memory would need to be paged out to make room for the page to be brought in from the disk. Then, the sparsely populated page is brought into the main memory from the disk, and the block needed used, after which it is almost immediately written back out to the disk. It can be seen that this produces a great deal of "thrashing", involving rapid, frequent disk fetch and write operations, and is undesirable since it greatly slows down memory operations.
What is needed is a method for managing a memory in which blocks are efficiently stored in a manner by which those which are infrequently needed are collected and compactly stored and paged out into disk, and blocks which are frequently used are collected and maintained in main memory for efficient access.
One method which has been proposed is taught in copending U.S. patent application entitled "METHOD FOR MANAGING VIRTUAL MEMORY TO SEPARATE ACTIVE AND STABLE MEMORY BLOCKS" by Bartley et al., Ser. No. 634,334, filed July 24, 1984, now U.S. Pat. No. 4,660,130, assigned to the assignee hereof, and incorporated herein by reference. Said patent discloses a method for compacting blocks of memory in a demand-paged, virtual address space which includes a plurality of virtual address pages. The method includes the steps of identifying active and stable blocks to be compacted by defining a pointer, N, to indicate an address of the virtual memory space and advancing the pointer, N, to continually indicate the address of the beginning of available virtual memory space. As new blocks are allocated, they are located in the virtual address space beginning at the location of the advancing pointer. Additionally, as blocks are referenced by the user, they are moved to the current location of the advancing pointer, so that, therefore, active blocks are collected together on active pages.
In one aspect of the method of the invention of said Bartley et al. patent, the extent of utilization of each page is determined, and blocks to which reference is made by the user are moved only if the extent of utilization of the page on which the referenced blocks are located falls below a predetermined level. Furthermore, a disk memory is provided, and periodically, the pages containing collected stable blocks are "paged-out" to it.
In accordance with still another aspect of said Bartley et al. patent, an associative look-up table is provided into which is written the identification and location of blocks which are moved to a special page which will eventually be paged-out. Also maintained in each table entry is a reference count of each block identified therein. The associative look-up table is periodically scanned to update references to the blocks identified in it.